package leecode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author csp 2021-04-28
 */
public class Question15 {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();
        if (nums.length < 3) {
            return list;
        }
        Arrays.sort(nums);
        for (int i = 0; i < nums.length-2; i++) {
            if(nums[i] > 0) break;
            if(i > 0 && nums[i] == nums[i - 1]) continue;
            int p1 = i + 1, p2 = nums.length - 1;
            while (p1 < p2) {
                int sum = nums[i] + nums[p1] + nums[p2];
                if (sum== 0) {
                    list.add(Arrays.asList(nums[i], nums[p1], nums[p2]));
                    while (p1 < p2 && nums[p1] == nums[++p1]) {}
                    while (p1 < p2 && nums[p2] == nums[--p2]) {}
                } else if (sum > 0) {
                    p2--;
                } else {
                    p1++;
                }
            }
        }
        return list;
    }


    public static void main(String[] args) {
        Question15 question15 = new Question15();
        final List<List<Integer>> lists = question15.threeSum(new int[]{-4,-2,1,-5,-4,-4,4,-2,0,4,0,-2,3,1,-5,0});
        System.out.println(Arrays.toString(lists.toArray()));
    }
//    public void sum(int l, int r, int i,int[] nums) {
//
//
//    }
}
